
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;


/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:38917
 * Date:2025/4/8
 * Time:20:04
 */
public class Solution {
    public static int[][] merge(int[][] intervals) {
        if (intervals.length == 0) return new int[0][2];
        //按照子数组的左端点的大小进行排序
        Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
        //创建顺序表来存放子数组
        List<int[]> ret = new ArrayList<>();
        //遍历二维数组
        for (int[] interval : intervals) {
            int left = interval[0];
            int right = interval[1];
            //当ret为空或者ret中最后一个元素的 右端点 小于 当前left时,向ret添加元素
            if (ret.isEmpty() || ret.get(ret.size() - 1)[1] < left) {
                ret.add(new int[]{left, right});
            } else {
                //将ret中最后一个元素的右端点和right比较,取较大值代替ret中最后一个元素的右端点
                ret.get((ret.size() - 1))[1] = Math.max(ret.get(ret.size() - 1)[1], right);
            }
        }
        //将顺序表转换为二维数组
        return ret.toArray(new int[ret.size()][]);
    }
    public static void main(String[] args) {
        int[][] array = {{1,3},{2,6},{8,10},{15,18}};
        int[][] ret = merge(array);
        for (int[] intS : ret) {
            for (int anInt : intS) {
                System.out.print(anInt + " ");
            }
        }
    }
}